package maxSubArray;

public class Solution {
    public int maxSubArray(int[] nums) {
        // 前缀和 + 枚举
//        for (int i = 1; i < nums.length; i++) {
//            nums[i] = nums[i-1] + nums[i];
//        }
//        int max = Integer.MIN_VALUE;
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                max = Math.max(nums[j] - nums[i],max);
//            }
//        }
//        return max;

        // 时间复杂度为O(n)
        // dp[i] 表示以第i项结尾面的最大的连续和
        // dp[i] = max(dp[i-1]+nums[i],nums[i])
//        int n = nums.length;
//        int[] dp = new int[n];
//        dp[0] = nums[0];
//        int ans = dp[0];
//        for (int i = 1; i < n; i++) {
//            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
//            ans = Math.max(ans,dp[i]);
//        }
//        return ans;

        // 动态规划
        int prev = nums[0],ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int cur = Math.max(prev + nums[i],nums[i]);
            ans = Math.max(cur,ans);
            prev = cur;
        }
        return ans;
    }
}
